Vahid Halilhodžić
Sita e Eratostenit është një algoritëm i thjeshtë dhe mjaft i vjetër për gjetjen e numrave të thjeshtë më të vegjël se një numër i caktuar natyral.Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers," Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347. Ai është shum efikas për numrat më të vegjël se 10 milion).The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008. Algoritmi u zbulua nga matematikani antik grek Eratosteni. Nicomachus, Introduction to Arithmetic, I, 13. http://www.archive.org/stream/nicomachigerasen00nicouoft#page/29/mode/1up Algoritmi Numri i thjeshtë është numri i cili ka pikërisht dy pjestues numrin 1 dhe vetvehten. Për të gjetur numrat e thjeshtë më të vegjël ose të barabartë me numrin e dhëne sipas metodës së Eratostenit kemi: # Krijojmë listën e të gjithë numrave natyral prej numrit 2 deri te numri i dëshiruar n'': (2, 3, 4, ..., ''n). # Numri i parë i thjeshtë është 2. # I flakim nga lista të gjithë shumfishat e p'' më të vegjël ose të barabartë me ''n. # E vërejmë numrin e mbetur në listë që është më i madh se p'' (ai është i thjeshtë); e zëvendësojmë atë me ''p. # Hapat 3 dhe 4 i përsërisim derisa p''2 është më i madh se ''n. # Të gjithë numrat e mbetur janë të thjeshtë. Shembull Për të gjetur numrat e thjeshtë më të vegjël se 30 veprojmë kështu: E shkruajmë listën e numrave natyral nga 2 deri në 30: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 I largojmë shumfishat e dyshit atëherë kemi listën: 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Numri i parë pas 2 është 3 ai është i thjeshtë, në vazhdim i largojmë shumfishat e 3 atëherë kemi listën: 2 3 5 7 11 13 17 19 23 25 29 Numri që vjen pas 3 është 5 i cili është i thjeshtë pastaj nga lista e mësipërme i largojmë shumfishat e 5 dhe atëherë fitojmë këtë listë: 2 3 5 7 11 13 17 19 23 29 Numri që vjen pas 5 është 7 por pasi 7^2=49 >30 procesi këtu përfundon që do të thotë se në listën e mësipërme të gjithë numrat janë të thjeshtë dhe më të vegjël se 30. Referencat Lidhje të jashtme * Sieve of Eratosthenes in C * Sieve of Eratosthenes in PHP * Analyze the Sieve of Eratosthenes in an online Javascript IDE * Interactive JavaScript Page * Sieve of Eratosthenes nga George Beck. * Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations. bg:Решето на Ератостен bs:Eratostenovo sito ca:Sedàs d'Eratòstenes cs:Eratosthenovo síto da:Eratosthenes' si de:Sieb des Eratosthenes en:Sieve of Eratosthenes eo:Kribrilo de Eratosteno es:Criba de Eratóstenes fa:غربال اراتوستن fi:Eratostheneen seula fr:Crible d'Ératosthène he:הנפה של ארטוסתנס hr:Eratostenovo sito hu:Eratoszthenész szitája id:Saringan Eratosthenes it:Crivello di Eratostene ja:エラトステネスの篩 ka:ერატოსთენეს საცერი ko:에라토스테네스의 체 lt:Eratosteno rėtis mk:Ератостеново сито nl:Zeef van Eratosthenes no:Eratosthenes' sil pl:Sito Eratostenesa pt:Crivo de Eratóstenes ro:Ciurul lui Eratostene ru:Решето Эратосфена scn:Criveddu d'Eratòstini sh:Eratostenovo sito simple:Sieve of Eratosthenes sk:Eratostenovo sito sl:Eratostenovo sito sr:Ератостеново сито sv:Eratosthenes såll tr:Eratosten kalburu uk:Решето Ератосфена zh:埃拉托斯特尼筛法